from tools_algorithm import *


class Solution:
    def shortestSubstrings(self, arr: List[str]) -> List[str]:
        cnt = Counter()
        for a in arr:
            for i in range(len(a)):
                for j in range(i + 1, len(a) + 1):
                    cnt[a[i:j]] += 1
        ans = []
        for a in arr:
            for i in range(len(a)):
                for j in range(i + 1, len(a) + 1):
                    c = a[i:j]
                    cnt[c] -= 1
            s = None
            for i in range(len(a)):
                for j in range(i + 1, len(a) + 1):
                    c = a[i:j]
                    if cnt[c] == 0 and (
                        s is None or len(c) < len(s) or (len(c) == len(s) and c < s)
                    ):
                        s = c
            for i in range(len(a)):
                for j in range(i + 1, len(a) + 1):
                    cnt[a[i:j]] += 1
            ans.append(s if s is not None else "")
        return ans


s = Solution()
print(s.shortestSubstrings(["gfnt", "xn", "mdz", "yfmr", "fi", "wwncn", "hkdy"]))
